package effizienz;

public class Rucksack {
  public static void main(String[] args){
    int[] gold;
    int voll;
    if(args.length==0){
      voll=150;
      gold=new int[]{4,7,11,12,15,22,23,43,52,51,52,58};
    } else{
      voll=Integer.parseInt(args[0]);
      gold=new int[args.length-1];
      for(int i=1; i<args.length; ++i)
        gold[i-1]=Integer.parseInt(args[i]);
    }
    nimm=new boolean[gold.length];
    if(kombi_rek(voll, gold))
      System.out.println(goldkette(gold, nimm));
  }

  public static boolean[] nimm;//initialisiert mit gleicher length wie gold
  
  public static boolean kombi_rek(int voll, int[] gold){
    return do_kombi(voll, gold, 0) || do_kombi(voll, gold, 0);
  }
  
  private static boolean do_kombi(int voll, int[] gold, int ab){
    if(ab>=gold.length) return summe(gold, nimm)==voll;
    nimm[ab]^=true;
    return do_kombi(voll, gold, ab+1) || do_kombi(voll, gold, ab+1);
  }
  
  public static boolean kombi_iter(int voll, int[] gold){
    int i=-1;
    while(++i<nimm.length)
      if(nimm[i]^=true)
        if(summe(gold, nimm)==voll) return true;
        else i=-1;
    return false;//Füllung unmöglich
  }

  public static int summe(int[] gold, boolean[] nimm){
    int summe=0;
    for(int i=0; i<nimm.length; ++i)
      if(nimm[i]) summe+=gold[i];
    return summe;
  }
  
  public static String goldkette(int[] gold, boolean[] nimm){
    StringBuffer erg=new StringBuffer();
    for(int i=0; i<nimm.length; ++i)
      if(nimm[i]) erg.append(gold[i]+" ");
    return erg.toString();
  }
}
